#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAXSIZE 10

/* Stack */
typedef struct SNode* PtrToSNode;
struct SNode {
    int data[MAXSIZE];
    int top;
    int maxsize;
};
typedef PtrToSNode Stack;

Stack CreateStack () {
    Stack S = (Stack)malloc(sizeof(struct SNode));
    memset(S->data,0,MAXSIZE);
    S->top = -1;
    S->maxsize = MAXSIZE;
    return S;
}

bool StackEmpty ( Stack S ) {
    return ( S->top == -1 );
}

bool StackFull ( Stack S ) {
    return ( S->top == ( S->maxsize - 1 ) );
}

void Push ( Stack S, int X ) {
    if ( StackFull(S) ) {
        printf("Stack Full\n");
        return;
    }
    S->data[++(S->top)] = X;
}

int Pop ( Stack S ) {
    if ( StackEmpty(S) ) {
        printf("Stack Empty\n");
        exit(-2);
    }
    return (S->data[(S->top)--]);
}

/* Queue */
struct QNode {
    int *Data;     /* 存储元素的数组 */
    int Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

Queue CreateQueue()
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (int*)malloc(MAXSIZE * sizeof(int));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MAXSIZE;
    return Q;
}

bool QueueFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}

bool AddQ( Queue Q, int X )
{
    if ( QueueFull(Q) ) {
        printf("Queue Full\n");
        return false;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return true;
    }
}

bool QueueEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}

int DeleteQ( Queue Q )
{
    if ( QueueEmpty(Q) ) { 
        printf("Queue Empty\n");
        exit(-4);
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return Q->Data[Q->Front];
    }
}

// typedef struct QNode* PtrToQNode;
// struct QNode {
//     int data[MAXSIZE];
//     int front, rear;
//     int maxsize;
// };
// typedef PtrToQNode Queue;

// Queue CreateQueue () {
//     Queue Q = (Queue)malloc(sizeof(struct QNode));
//     memset(Q->data,0,MAXSIZE);
//     Q->front = Q->rear = 0;
//     Q->maxsize = MAXSIZE;
//     return Q;
// }

// bool QueueFull ( Queue Q ) {
//     return ( ( Q->rear + 1 ) % Q->maxsize == Q->front );
// }

// bool QueueEmpty ( Queue Q ) {
//     return ( Q->front == Q->rear );
// }

// void AddQ ( Queue Q, int X ) {
//     if ( QueueFull(Q) ) {
//         printf("Queue Full\n");
//         return;
//     }
//     Q->rear = (Q->rear+1) % Q->maxsize;
//     Q->data[Q->rear] = X;
// }

// int DeleteQ ( Queue Q ) {
//     if ( QueueEmpty(Q) ) {
//         printf("Queue Empty\n");
//         exit(-3);
//     }
//     int X;
//     X = Q->data[Q->front];
//     Q->front = (Q->front+1) % Q->maxsize;
//     return X;
// }

/* Graph */
typedef struct GNode* PtrToGNode;
struct GNode {
    int Nv;/* point */
    int Ne;/* edge */
    int G[MAXSIZE][MAXSIZE];
};
typedef PtrToGNode Graph;

typedef struct ENode* PtrToENode;
struct ENode {
    int N1, N2;
    int weight;
};
typedef PtrToENode Edge;

Graph CreateGraph ( int Nv ) {
    int i, j;
    Graph G = (Graph)malloc(sizeof(struct GNode));
    G->Nv = Nv;
    G->Ne = 0;
    for ( i = 0; i < Nv; i++ ) 
        for ( j = 0; j < Nv; j++ ) 
            G->G[i][j] = 0;
    return G;
}

Graph AddEdge ( Graph G, Edge E ) {
    G->G[E->N1][E->N2] = E->weight;
    G->G[E->N2][E->N1] = E->weight;
    return G;
}

Graph BuildGraph () {
    int i, Nv, Ne;
    scanf("%d %d", &Nv, &Ne);
    Graph G = CreateGraph(Nv);
    Edge E = (Edge)malloc(sizeof(struct ENode));
    for ( i = 0; i < Ne; i++ ) {
        scanf("%d %d", &E->N1, &E->N2);
        E->weight = 1;
        AddEdge(G,E);
    }
    free(E);
    return G;
}

void BFS ( int* visit, Queue Q, Graph G, int N ) {
    int i, j;
    for ( i = 0; i < G->Nv; i++ ) {
        if ( G->G[N][i] == 1 ) {
            if ( visit[i] == 0 ) {
                visit[i] = 1;
                AddQ(Q,i);
            }
        }
    }
}

// void DFS ( int* visit, Stack S, Graph G, int N ) {
//     int i, j;
//     for ( i = 0; i < G->Nv; i++ ) {
//         if ( G->G[N][i] == 1 ) {
//             if ( visit[i] == 0 ) {
//                 visit[i] = 1;
//                 Push(S,i);
//             }
//         }
//     }
// }

void DFS ( int* visit, Stack S, Graph G, int N ) {
    int i, j;
    for ( i = ((G->Nv)-1); i >= 0; i-- ) {
        if ( G->G[N][i] == 1 ) {
            if ( visit[i] == 0 ) {
                visit[i] = 1;
                Push(S,i);
            }
        }
    }
}

int main () {
    int i, X;
    /* Build Graph */
    Graph G = BuildGraph();
    /* DFS */
    int* visit = (int*)malloc(sizeof(int)*G->Nv);
    memset(visit,0,sizeof(int)*(G->Nv));
    Stack S = CreateStack();
    for ( i = 0; i < G->Nv; i++ ) {
        if ( visit[i] == 1 ) continue; 
        printf("{");
        visit[i] = 1;
        Push(S,i);
        while ( !StackEmpty(S) ) {
            X = Pop(S);
            printf(" %d", X);
            DFS(visit, S, G, X);
        }
        printf(" }\n");
    }
    free(S);
    /* BFS */
    memset(visit,0,sizeof(int)*(G->Nv));
    Queue Q = CreateQueue();
    for ( i = 0; i < G->Nv; i++ ) {
        if ( visit[i] == 1 ) continue; 
        printf("{");
        visit[i] = 1;
        AddQ(Q,i);
        while ( !QueueEmpty(Q) ) {
            X = DeleteQ(Q);
            printf(" %d", X);
            BFS(visit, Q, G, X);
        }
        printf(" }\n");
    }
    free(Q);

    /* Free Graph */
    free(visit);
    free(G);
    return 0;
}